package com.leetcode.partition11;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/10 9:18
 */
public class LC1049最后一块石头的重量2 {

    public static int lastStoneWeightII(int[] stones) {
        return dynamicProgramming(stones);
    }

    public static void main(String[] args) {
        int[] stones = {2, 7, 4, 1, 8, 1};
        System.out.println(lastStoneWeightII(stones));
    }

    private static int dynamicProgramming(int[] stones) {
        //转换为01背包问题，求两堆石头的最小差值，则问题转换成了背包最多装sum / 2的石头，stones数组里面有一堆石头，如何装下最多石头
        int sum = 0;
        for (int stone : stones) sum += stone;
        int capaticy = sum >> 1;
        int[] dp = new int[capaticy + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = capaticy; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return sum - (dp[capaticy] << 1);
    }
}
